package problem300;

import java.util.ArrayList;

//300.最长递增子序列
//https://leetcode.cn/problems/longest-increasing-subsequence/

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        ArrayList<Integer> ret = new ArrayList<>();
        ret.add(nums[0]);
        for(int i = 1; i<n; i++) {
            if(nums[i] > ret.get(ret.size()-1)) {
                ret.add(nums[i]);
            }else {
                int index = binarySearch(ret, nums[i]);
                ret.set(index, nums[i]);
            }
        }
        return ret.size();
    }
    public int binarySearch(ArrayList<Integer> ret, int target) {
        int left = 0, right = ret.size()-1;
        while(left < right) {
            int mid = left + (right-left)/2;
            if(ret.get(mid) < target) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return left;
    }
}